#include<iostream>

using namespace std;

/**
 * Definition for singly-linked list.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/*
 * 设计思路: 将两个单项链表中的数字取出,分别组合成整数.然后,将两个整数相加,得到和sum.
 *          最后,再将sum拆分成数字,按照低位在前,高位在后的原则,插入到链表中.
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum = 0;
        int rem = 0;
        int carry = 0;
        ListNode *node1Ptr = l1;
        ListNode *node2Ptr = l2;

        do {
            int val_1 = (node1Ptr!=nullptr)?(node1Ptr->val):(0);
            int val_2 = (node2Ptr!=nullptr)?(node2Ptr->val):(0);
            sum = val_1 + val_2 + carry;

            rem = sum % 10;
            carry = sum / 10;

            if (node1Ptr ) {
                node1Ptr->val = rem;
                if (!node1Ptr->next) {
                    if ( !node2Ptr || (node2Ptr && !node2Ptr->next)) {
                        if (carry) {
                            node1Ptr->next = l2;
                            node1Ptr->next->val = carry;
                            node1Ptr->next->next = nullptr;
                        }
                        return l1; 
                    }
                }
                node1Ptr = node1Ptr->next;
            }

            if (node2Ptr) {
                node2Ptr->val = rem;
                if (!node2Ptr->next ) {
                    if ( !node1Ptr) {
                        if (carry) {
                            node2Ptr->next = l1;
                            node2Ptr->next->val = carry;
                            node2Ptr->next->next = nullptr;
                        }
                        return l2; 
                    }
                }
                node2Ptr = node2Ptr->next;
            }
        } while(node1Ptr || node2Ptr);

        return nullptr;
    }

    ListNode* addTwoNumbers_1(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
    }
};

bool testCase(int num1, int* ptr1, int num2, int* ptr2)
{
    Solution newSolution;

    ListNode *tmpNode1 = nullptr;
    ListNode *tmpNode2 = nullptr;

    for(int i = num1; i>0; i--) {
        tmpNode1 = new ListNode(*(ptr1+i-1), tmpNode1);
        cout << tmpNode1->val << ",";
    }
    cout << endl;

    for(int i = num2; i>0; i--) {
        tmpNode2 = new ListNode(*(ptr2+i-1), tmpNode2);
        cout << tmpNode2->val << ",";
    }
    cout << endl;

    tmpNode1 = newSolution.addTwoNumbers(tmpNode1, tmpNode2);
    
    do {
        cout << tmpNode1->val << ",";
        tmpNode1 = tmpNode1->next;
    } while(tmpNode1);
    cout << endl;

    return 0;
}

int main(void)
{
    cout << "test_case_1:" << endl;
    int input_case1_1[3] = {2,4,3};
    int input_case1_2[3] = {5,6,4};
    if(!testCase(3, input_case1_1, 3, input_case1_2)) {
        cout << "test_case_1: ok" << endl;
    }

    // 测试用例2
    cout << "test_case_2:" << endl;
    int input_case2_1[7] = {9,9,9,9,9,9,9};
    int input_case2_2[4] = {9,9,9,9};
    if(!testCase(7, input_case2_1, 4, input_case2_2)) {
        cout << "test_case_2: ok" << endl;
    }

    // 测试用例3
    cout << "test_case_3:" << endl;
    int input_case3_1[31] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1};
    int input_case3_2[3] = {5,6,4};
    if(!testCase(31, input_case3_1, 3, input_case3_2)) {
        cout << "test_case_3: ok" << endl;
    }

    // 测试用例4
    cout << "test_case_4:" << endl;
    int input_case4_1[3] = {2,4,9};
    int input_case4_2[4] = {5,6,4,9};
    if(!testCase(3, input_case4_1, 4, input_case4_2)) {
        cout << "test_case_4: ok" << endl;
    }

    // 测试用例5
    cout << "test_case_5:" << endl;
    int input_case5_1[1] = {5 };
    int input_case5_2[1] = {5 };
    if(!testCase(1, input_case5_1, 1, input_case5_2)) {
        cout << "test_case_5: ok" << endl;
    }

    cout << "test_case_6:" << endl;
    int input_case6_1[1] = {0 };
    int input_case6_2[2] = {7,3};
    if(!testCase(1, input_case6_1, 2, input_case6_2)) {
        cout << "test_case_6: ok" << endl;
    }

    cout << "test_case_7:" << endl;
    int input_case7_1[2] = {1,8};
    int input_case7_2[1] = {0};
    if(!testCase(2, input_case7_1, 1, input_case7_2)) {
        cout << "test_case_7: ok" << endl;
    }

    return 0;
}

// g++ -g -Wall -std=c++11 2_add-two-numbers.cpp